/*
*2014年06月05日18:25:27
*
*@路家豪
*
*操作系统作业：基于优先级的进程调度算法模拟实现
*
*环境：Ubuntu14.04 32bit
*工具：gcc 4.8.2
*/
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
typedef struct node /*创建PCB*/      
{   
	char name[10];  /*进程标识*/
	int prio;   /*进程优先数*/
	int cputime; /*进程占用CPU时间*/
	int needtime; /*进程完成所需时间*/
	int count;  /*计数器*/
	char state; /*进程的状态*/
	struct node *next; /*链指针*/
}PCB;
PCB *finish,*ready,*tail,*run;
int N;
void firstin()          /*创建就绪队列对头指针*/
{
   	run=ready;   
   	run->state='R';   
   	ready=ready->next;  
}
void prt()  /*演示进程调度*/
{
   	PCB *p;
   	printf("进程标识 占用CPU时间 完成用时 优先权 进程状态\n"); 
   	if(run!=NULL) 
   	printf("  %-10s%-10d%-10d%-10d %c\n",run->name,run->cputime,run->needtime,run->prio,run->state);  
   	p=ready;  
   	while(p!=NULL)
   	{ 
		printf("  %-10s%-10d%-10d%-10d %c\n",p->name,p->cputime,p->needtime,p->prio,p->state); 
      		p=p->next;
   	}
   	p=finish;  
   	while(p!=NULL)
   	{  
		printf("  %-10s%-10d%-10d%-10d %c\n",p->name,p->cputime,p->needtime,p->prio,p->state); 
      		p=p->next;
   	}
   	getchar();  
}
void insert(PCB *q)	/*插入就绪队列中*/
{
	PCB *p1,*s,*r;
	int b;
   	s=q;
   	p1=ready;
   	r=p1;
   	b=1;
   	while((p1!=NULL)&&b)
      	if(p1->prio>=s->prio)
      	{
     		r=p1;
     		p1=p1->next;
      	}
      	else
     	b=0;
   	if(r!=p1)
   	{
      		r->next=s;
      		s->next=p1;
   	}
   	else
   	{
      		s->next=p1;
      		ready=s;
   	}
}
void create()   /*创建各个进程*/
{
   	PCB *p;
   	int i,time;//进程需要执行的时间
   	char na[10];//进程的名称
   	ready=NULL;//队列的首尾指针都为空
   	finish=NULL;
   	run=NULL;
    	for(i=1;i<=N;i++)
   	{
      		p=malloc(sizeof(PCB));//动态分配内存
      		printf("输入进程的名称:\n");
      		scanf("%s",na);
      		printf("输入进程需要执行的时间(最好小于50秒):\n");
      		scanf("%d",&time);
      		strcpy(p->name,na);//将输入的进程名称复制到动态分配的内存中
      		p->cputime=0;
      		p->needtime=time;
      		p->state='w';
      		p->prio=50-time;  /*假设优先级与耗时之和为50*/
      		if(ready!=NULL)
        		insert(p);
      		else
      		{
     			p->next=ready;
     			ready=p;
      		}
   	}
   	system("clear"); 
   	printf("          显示所有进程:\n");
   	printf("************************************************\n");
   	prt();
   	run=ready;
   	ready=ready->next;
   	run->state='R';
}
void priority()   /*优先级算法调度*/
{
   	while(run!=NULL&&run->prio>=0)
   	{
      		run->cputime=run->cputime+1;
      		run->needtime=run->needtime-1;
      		run->prio=run->prio-3;
      		if(run->needtime==0)
      		{
        		run->next=finish;
        		finish=run;
        		run->state='F';
        		run=NULL;
        		if(ready!=NULL)
          			firstin();
      		}
      		else	if((ready!=NULL)&&(run->prio<ready->prio))
     		{
        		run->state='W';
        		insert(run);
        		firstin();
     		}
      		prt();
   	}
}
int main(int argc, char **argv)
{  
	system("clear");//清屏
   	printf("请输入PCB的总数(少输入几个，cpu也累啊):\n");
   	scanf("%d",&N);//pcb总数
   	create();//创建pcb
   	priority();
	return 0;
}
